1. Field of the Invention
The present invention relates generally to a computerized method and system for providing a solution to any general (non-convex) minimum-maximum problem in constrained optimization in any specific application. In an exemplary application, the technique is used to demonstrate optimal design of three-dimensional parts for manufacturing, constrained by prescribed tolerances.
2. Description of the Related Art
The present invention is introduced by first setting forth the following known construct:
Given a function y=f(x,c)=c1x1+c2x2, where x is a set of independent variables x={x1,x2}, x1 and x2 are subsets of x, c={c1,c2} is a set of functional parameters, partitioned into two subsets c1 and c2, and y is a dependent variable, it is desired to minimize (over x2) the maximum (over x1) of y, subject to a linear constraint A12x1+A21x2≦b12, where A12, A21 are sub-matrices and b12 is a vector.
This means finding appropriate values for vectors c1 and c2, so as to solve:Min{c2x2+Max c1x1}, subject to A12x1+A21x2≦b12.
This problem is, therefore, associated with a linear constraint set and a piece-wise linear objective function. FIG. 1 graphically depicts the problem, wherein are shown axes x1 and x2, representing two sets of control/decision variables. Variable x1 might represent, for example, the tolerances for various components to be manufactured, in which a simple 3-D component is associated with three tolerance variables, one for each dimension. Variable x2 then describes the costs of manufacturing the components as a function of the components' tolerance specifications.
In this setting, the tighter the values of a component's tolerance variables, the better is the degree of precision achieved in the component. But, at the same time, it is more costly to manufacture the component.
The vector C=(c1, c2) captures the sensitivity of the two sets of decisions x1 and x2 that can be used to calculate the overall manufacturing design efficiency. The polyhedron P, label 100, describes the set of all feasible (x1, x2) values that satisfy all engineering and other design requirements (as specified by the tolerance parameters matrix, A=[A12, A21]) to manufacture the components.
The general problem is NP-hard and difficult to resolve in a reasonable time. The usual techniques used in attempting to arrive at a global optimum are Simulated Annealing, Genetic Algorithm or other Monte Carlo type approaches.
However, all of these techniques are slow, cumbersome, and do not guarantee a global solution.
The generalized min-max problem is characterized as a model for scenarios in which there are two conflicting objectives and a concave objective function providing an effectiveness/efficiency metric. Presently, no computerized tool is available that guarantees a global solution to the general min-max problem, let alone a computer tool that can find such solution in a reasonable time.